"""
问题一:   汉罗塔问题
 What are the rules of the Tower of Hanoi?
Tower of Hanoi is a mathematical puzzle where we have three rods and n disks. The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules: 
1.Only one disk can be moved at a time. 
2.Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack. 
3.No disk may be placed on top of a smaller disk.



1.n – the number of disks.
2.from_rod – The rod which has all the disks at the start.
3.to_rod – The rod to which all the disks has to be moved.
4.aux_rod – The auxiliary rod which can be used to place the disks temporarily.
"""

def TowerOfHanoi(n , source, destination, auxiliary):
    if n==1:
        print ("Move disk 1 from source",source,"to destination",destination)
        return
    TowerOfHanoi(n-1, source, auxiliary, destination)
    print ("Move disk",n,"from source",source,"to destination",destination)
    TowerOfHanoi(n-1, auxiliary, destination, source)
        # Driver coden = 4TowerOfHanoi(n,'A','B','C') # A, C, B are the name of rods



# Q6 八皇后问题:

N = 8 # (size of the chessboard)

def solveNQueens(board, col):
    if col == N:
        print(board)
        return True
    for i in range(N):
		if isSafe(board, i, col):
			board[i][col] = 1
			if solveNQueens(board, col + 1):
				return True
		    board[i][col] = 0
	return False

def isSafe(board, row, col):
	for x in range(col):
		if board[row][x] == 1:
			return False
	for x, y in zip(range(row, -1, -1), range(col, -1, -1)):
		if board[x][y] == 1:
			return False
	for x, y in zip(range(row, N, 1), range(col, -1, -1)):
		if board[x][y] == 1:
			return False
	return True

board = [[0 for x in range(N)] for y in range(N)]
if not solveNQueens(board, 0):
	print("No solution found")
#八皇后问题的解法2
# Taking number of queens as input from user
print ("Enter the number of queens")
N = int(input())

# here we create a chessboard
# NxN matrix with all elements set to 0
board = [[0]*N for _ in range(N)]

def attack(i, j):
    #checking vertically and horizontally
    for k in range(0,N):
        if board[i][k]==1 or board[k][j]==1:
            return True
    #checking diagonally
    for k in range(0,N):
        for l in range(0,N):
            if (k+l==i+j) or (k-l==i-j):
                if board[k][l]==1:
                    return True
    return False

def N_queens(n):
    if n==0:
        return True
    for i in range(0,N):
        for j in range(0,N):
            if (not(attack(i,j))) and (board[i][j]!=1):
                board[i][j] = 1
                if N_queens(n-1)==True:
                    return True
                board[i][j] = 0

    return False

N_queens(N)
for i in board:
    print (i)

